I. Database searches
A computerized database is a collection of information that is organized for ease of retrieval. Such databases are generally organized in a structured pattern. One such structure is known as a TRIE-structure.
In a traditional TRIE-structured database information is located through searches that employ TRIE-nodes. Such TRIE-nodes are supported by memory, and each contains a list, e.g., of sixteen elements, each element corresponds to one of sixteen possible characters.
Using such a TRIE-structure, string words of arbitrary length may be searched. First, the string word being searched is divided into several characters, each being four bits in length for the above example (i.e., a sixteen element node). Next, the first character of the word being searched is used to index into the first TRIE-node.
The element corresponding to the character being searched may be one of three types:
(1) The element may be a NODE pointer which points to another TRIE-node. A NODE pointer indicates that, as of the character being searched, an entry in the database matches the string word being searched. If a NODE pointer is found using the first character as an index into the first node, the second character in the string word is then used to index into the node referenced by the NODE pointer. If another NODE pointer is found, the process repeats, this time using the third character of the string word as an index.
(2) The second type of element which may be referenced in a node is a NIL or NULL pointer. A NIL pointer indicates that the database holds no entries that match the string being searched beyond this point. When a NIL pointer is found, the search stops.
(3) The third possible element in a node is a LEAF pointer. A LEAF pointer indicates that a match has been found with an element in the database, and that no more searching is required. A LEAF pointer marks the end of a successful search, and may point to the start of some other process.
A example of a search using a traditional TRIE-structured database is given in FIG. 1. FIG. 1 illustrates a traditional TRIE structured database (10). The TRIE-structure includes nodes A (11), B (13), C(15), and D (17). String word (00) is illustrated as an exemplary word to be searched. As may be seen, string word (00) is divided into four characters (01,02,03,04) each four bits in length.
The first character (01) is used to index into the first node, node A (11). Since the first character is 1110, or E in hexi-decimal (hereinafter Eh), the fifteenth element (12) is checked. In the example the element corresponding to Eh (12) contains a NODE pointer which points to node B (13). Thus, the search continues at node B.
The second character of the string word (02), Ah, is used to index into node B (13) where another node pointer is found. This pointer points to node C and thus the search continues at node C using the third character (03), 8h, of the search word. In node C, the element corresponding to 8h is a pointer to node D.
The process continues until at node D (17) a LEAVE pointer is found in the element corresponding to the fourth character (04), 3h. At this point the search is complete, and the process referenced by the LEAF pointer is begun.
Had the fourth character of the string word been a 0h, the element corresponding to 0h (18) would have been selected. Since a NIL pointer is located at this element, the search would have been terminated as there is no element in the database that matches such a string word.